// 8_15.c
#include <stdio.h>
#define NUMEL 7

int main()
{
    int nums[NUMEL] = {98, 32, 45, 99, 101, 73, 67};
    int i, pivot;
    int partition(int[], int, int); /*function prototype*/

    pivot = partition(nums, 0, NUMEL - 1);

    printf("The returned pivot index is %d\n",pivot);
    printf("The list is now in the order:\n");
    for (i = 0; i < NUMEL; i++)
        printf("%d ", nums[i]);
printf("\n");

    return 0;
}

int partition(int num[], int left, int right)
{
    int pivot, temp;
    pivot = num[left]; /*"capture" the pivot value, which frees up one slot*/
    while (left < right)
    {
        /*scan from right to left*/
        while (num[right] >= pivot && left < right)
            right--;
        if (right != left)
        {
            num[left] = num[right];
            left++;
        }
        /*scan from left to right*/
        while (num[left] <= pivot && left < right)
            left++;
        if (right != left)
        {
            num[right] = num[left];
            right--;
        }
    }
    num[left] = pivot;
    return(left);
}
